/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.linkedlist;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * <p>
 * 合并k个有序链表
 * 时间复杂度n*k*log(k)
 * </p>
 * @author towan
 * @email tongwenzide@163.com
 * 2015年5月24日
 */
public class MergeKSortedLists {

 public ListNode mergeKLists(ListNode[] lists) {
     if(lists==null || lists.length ==0){
         return null;
     }
     /**
      * 
      * <p>链表的排序器</p>
      * @author towan
      * @email tongwenzide@163.com
      * 2015年5月24日
      */
     class MyComparator implements Comparator<ListNode>{

         /* (non-Javadoc)
          * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
          */
         @Override
         public int compare(ListNode o1, ListNode o2) {
             if(o1.val<o2.val){
                 return -1;
             }else if(o1.val>o2.val){
                 return 1;
             }else{
                 return 0;
             }
         }
         
     }

     //建立一个堆，升序排列
     PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(lists.length,new MyComparator());
     ListNode head = null;
     ListNode cur = null;
     //向堆加入每个链表的表头
     for(int i= 0;i<lists.length;i++){
         if(lists[i]!=null){
             heap.add(lists[i]);
         }
     }
     while(!heap.isEmpty()){
         if(head == null){//找到第一个节点
             head = heap.poll();
             cur = head;
             if(cur.next!=null){
                 heap.add(cur.next);
             }
         }else{
             ListNode newNode = heap.poll();
             cur.next = newNode;//把输出链表链接起来
             cur = newNode;
             if(cur.next!=null){
                 heap.add(cur.next);
             }
         }
     }
        return head;
    }
}
